﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定⼀个字符串 s 和⼀个字符串数组 words。 words 中所有字符串 ⻓度相同。 
// s 中的 串联⼦串 是指⼀个包含  words 中所有字符串以任意顺序排列连接起来的⼦串。 
//例如，如果 words  =  [ab, cd, ef]， 那么 abcdef， abefcd，cdabef， cdefab，efabcd， 和 efcdab 都是串联⼦串。
// acdbef 不是串联⼦串，因为他不是任何 words 排列的连接。返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。

//eg: 
//输⼊：s  =  barfoothefoobarman,  words  =  [foo, bar] 
//输出：[0, 9] 

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

//思路：滑动窗口+哈希。和“找到字符串中所有字⺟异位词”这道题思路一样
void findSubstring(string s, vector<string>& words)
{
	unordered_map<string, int> hash1;//存储键值对关联容器
	for (auto str : words)
	{
		hash1[str]++;
	}
	int len = words[0].size(),n=words.size();
	for (int i = 0; i < len; i++)
	{
		unordered_map<string, int> hash2;
		for (int left = i, right = i,count=0; right + len < s.size(); right += len)
		{
			string in = s.substr(right,len);//进窗口
			hash2[in]++;
			if (hash2.count(in) && hash2[in] <= hash1[in])
				count++;
			while (right-left+1>n*len)//判断
			{
				string out = s.substr(left, len);	
				if (hash2.count(out) && hash2[out] <= hash1[out])//出窗口
					count--;
				hash2[out]--;
				left+=len;
			}
			if (count == n)//更新数据
				cout << left << ' ';
		}
	}
}

int main()
{
	string s("abcdefabcdefabcdef");
	vector<string> words = { "ab","cd","ef"};//动态数组
	cout << "s: " << s << "  " << "words: " ;
	for (auto str:words)
	{
		cout << str << ' ';
	}
	cout << endl;

	findSubstring(s,words);

	return 0;
}